This invention relates generally to packet-switching systems, such as asynchronous transfer mode (ATM) systems, and specifically to traffic shapers of such systems.
Today""s business communications environment consists of two separate network infrastructures: a voice network (such as a private branch exchange (PBX)) characterized by real-time, high-reliability, constant bit-rate (CBR) connections; and a data network (such as a packet network) characterized by high-bandwidth variable bit-rate (VBR) connections. Business needs for simplified maintenance, management, and access to information on diverse networks are forcing the convergence of these networks along with a new class of real-time multimedia networks. Asynchronous transfer mode (ATM) provides a single infrastructure that cost-effectively and flexibly handles both switching and transmission for the traffic types mentioned above (voice, video, and data) for both local-area networks and wide-area networks. The evolving network convergence requires the adaptation of the legacy PBX voice traffic to ATM. Voice telephony over ATM (VTOA) specifications allow adaptation of compressed or uncompressed voice pulse-code modulated (PCM) data streams into streams (virtual circuits) of CBR cells.
An ATM cell, regardless of the traffic it carries, is a packet 53 octets long: 48 octets of payload attached to a 5-octet header. The header contains addressing and management information used to direct the cell from source to destination and to ensure that the negotiated aspects of the traffic-flow through the ATM network are met. CBR traffic is assembled into cell payloads using ATM Adaptation Layer 1 (AAL1). The AAL1 cell constructor layer uses the first octet of the payload for its header and-the remaining 47 octets to carry CBR information. ATM cell construction is then completed by attaching the ATM header to the payload.
An individual ATM cell carries traffic of a single narrowband or wideband channel (a virtual circuit). Illustratively, a narrowband channel is represented by a single time slot of each successive frame of a TDM bus, while a wideband channel is represented by a plurality of time slots of each successive-frame of a TDM bus. If a transmitter handles a to plurality of virtual circuits, different ones of the ATM cells that it transmits carry traffic of different virtual circuits. Likewise, if a receiver handles a plurality of virtual circuits, different ones of the ATM cells that it receives carry traffic of different virtual circuits. A transmitter may transmit the traffic of different virtual circuits to different receivers. Likewise, a receiver may receive the traffic of different virtual circuits from different transmitters.
The traffic of each virtual circuit is processed by its own instance of the AAL1 cell constructor layer; the number of active instances varies as virtual circuits are added and removed. Assuming a channel carrying uncompressed pulse-code modulated (PCM) traffic having an 8 KHz sampling rate, each instance of the cell constructor that is processing a narrowband virtual circuit is supplied one PCM octet every 125 us frame period. It therefore requires 5.875 ms to fill a cell (47 octets * 125 us/octet). Fully constructed (mature) cells from all instances of the cell constructor are then transmitted.
Unlike the constant cell rate from narrowband virtual circuit, a wideband virtual circuit generates a constant average cell rate but a variable instantaneous cell rate. For example, a 32-narrowband-channel-wide wideband virtual circuit is supplied 32 octets during each frame period. The processing sequence effected by its cell constructor instance is as follows: during a first frame period, fill the first 32 octets of a first empty ATM cell; during a second frame period, fill the remaining 15 octets of the first ATM cell, transmit the first ATM cell, and fill the first 17 octets of a second empty ATM cell; during a third frame period, fill the-remaining 30 octets of the second cell, transmit the second cell, and fill the first 2 octets of a third empty cell; etc. This sequence shows an instantaneous cell rate of one cell every 250 us (two frame periods) sometimes and one cell every 125 us (one frame period) at other times. Variable bit-rate virtual circuits, whether narrowband or wideband, provide even greater diversity in the instantaneous cell rate.
ATM switches police cell traffic to ensure that it does not exceed the cell-traffic capacity of the switches. The average cell rate is policed on a per-switch basis, but the peak (instantaneous) cell rate is policed on a per-virtual-circuit basis. Receiving ATM switches delete received cells of each virtual circuit that exceed that virtual circuit""s negotiated peak cell rate. And transmitting ATM switches meter out cells from each virtual circuit to ensure that they do not exceed that virtual circuit""s negotiated peak cell rate.
The ATM standards specify a Generic Cell Rate Algorithm (GCRA) for use by both hardware and software-implemented devices, called traffic shapers, for metering out cells. The GCRA requires the traffic shapers to periodically process the output queue of each virtual circuit. The period may be different for each virtual circuit, and is a function of the negotiated peak cell rate for that virtual circuit. In the case of PCM traffic having an 8 KHz sampling rate, the processing period is the 125 us frame period. The queues of all virtual circuits are processed during each period. If the queue of a virtual circuit is empty, the traffic shaper does not transmit a cell from that queue. If a cell is available in the queue of a virtual circuit, the traffic shaper transmits it if it meets the GCRA criterion, i.e., if the period between the last transmitted cell from this queue and now is greater than or equal to the minimum administered cell-rate period. If more than one cell is available in the queue of a virtual circuit, the traffic shaper transmits one cell from the queue if it meets the GCRA criterion, and the next cell must wait at least until the subsequent processing period to be transmitted. A spacing of at least 125 us between transmitted ATM cells from any virtual circuit is thus ensured, thereby guaranteeing that the virtual circuit does not exceed its negotiated peak cell rate.
A problem with using the GCRA for multiple virtual circuits is that the traffic shapers must test the output queue of each virtual circuit during each processing period to determine if it has a cell to transmit. This is a particularly onerous task for GCRA implemented in software that supports large numbers (e.g., hundreds) of virtual circuits. Statistically, however, only one in 47 GCRA queue checks will result in the transmission of a cell during each processing period.
This invention is directed to solving these and other problems and disadvantages of the prior art. Generally according to the invention, traffic shaping for a plurality of streams of traffic (e.g. ATM virtual circuits or other packetized channels) utilizes a sequence of a first plurality of queues that are shared by the plurality of traffic streams, an enqueuing arrangement, and a dequeuing arrangement. Each of the traffic streams has at least one of the queues designated as its serving queue. Dequeuing is effected by cyclically transmitting contents of the sequence of the queues, i.e., by transmitting the contents of a different sequential one of the queues during each sequential period of the first plurality of such periods. During each period, a queue having a fixed offset in the sequence from the queue whose contents are being transmitted forms a current queue for that period. Preferably, the offset is zero, i.e., the current queue is the one whose contents are being transmitted. Enqueuing is effected as follows. In response to receipt of traffic (e.g., an ATM cell or another packet) from any said traffic stream during a period before a serving queue of that traffic stream becomes the current queue for that period, the received traffic is stored in that serving queue of that traffic stream. In response to receipt of traffic from any said traffic stream during a period when a serving queue of that traffic stream is the current queue for that period, the received traffic is stored in the current queue for that period. In response to receipt of traffic from any said traffic stream during a period after a serving queue of that traffic stream ceased being the current queue for that period, the received traffic is stored in the current queue for that period, and the designation of the at least one serving queue of that traffic stream is changed to designate the current queue of that period as a serving queue of that traffic stream. If a traffic stream has a plurality of serving queues, they are evenly spaced apart in the sequence of queues. The designation of the serving queues is then changed by shifting the designation from each of the serving queues a same distance in the sequence, to other queues that include the current queue. The shifting preferably involves shifting the designation a distance in the sequence from the serving queue of that traffic stream that last ceased being the current queue to the current queue, and shifting the designation from each of the other serving queues of that traffic stream a same distance to another queue.
This arrangement effects traffic shaping for both narrowband and wideband constant-bit-rate channels. For variable-bit-rate channels, an additional overflow queue is used, for temporarily storing any traffic received when enqueuing that traffic in the first plurality of queues would result in storing of that traffic in a queue that presently already stores received traffic of that traffic stream. When dequeuing has made room for storing the traffic that is presently stored in the overflow queue available in the first plurality of queues, enqueuing of that traffic in the first plurality of queues is then effected.
The above-characterized arrangement is very computationally-efficient. For example, while the GCRA of the prior art requires that as many queues as there are traffic streams be checked for an item of traffic to transmit during each dequeuing period, the subject arrangement requires that only one queue be checked and its contents be transmitted during each dequeuing period. Moreover, the subject arrangement often reduces the number of queues that are needed to effect traffic shaping. For example, in the case of an ATM system that transports only narrowband constant-bit-rate virtual circuits, only 47 queues are needed, regardless of how many of the virtual circuits there are. Although it is described below as providing traffic shaping for a plurality of ATM virtual circuits, it can be used for any packetized channels, including frame relay and voice over the Internet, and in fact is not precluded from serving non-packetized channels as well. And although it can be implemented in hardware, the subject arrangement is particularly suited for implementation in software, including firmware.
The invention includes both a method of as well as a corresponding apparatus, and a computer readable medium that contains software which, when executed in a computer, causes the computer to perform the method. The apparatus preferably includes an effectorxe2x80x94any entity that effects the corresponding step, unlike a meansxe2x80x94for each method step.
These and other features and advantages of the present invention will become more apparent from the following description of an illustrative embodiment of the invention considered together with the drawing.